Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Microsoft Hard Problems
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Sliding Window Maximum

Problem Statement

You are given an array of integers nums, and integer k, size of the sliding window which moves from the very left to the very right in the array. In each window, you can have only k numbers, and the window moves one position right by each time.

Return the array containing the maximum element of each sliding window.

Examples

Example 1:

  • Input: nums = [2, 1, 5, 1, 3, 2], k = 3
  • Expected Output: [5, 5, 5, 3]
  • Justification: Here, the window of size 3 moves across the array. The maximum values in each window are 5 (from [2, 1, 5]), 5 (from [1, 5, 1]), 5 (from [5, 1, 3]), and 3 (from [1, 3, 2]).

Example 2:

  • Input: nums = [4, -2, -3, 4, 1], k = 2
  • Expected Output: [4, -2, 4, 4]
  • Justification: The maximum values in each window of size 2 are 4 (from [4, -2]), -2 (from [-2, -3]), 4 (from [-3, 4]), and 4 (from [4, 1]).

Example 3:

  • Input: nums = [9, 7, 2, 4, 6], k = 4
  • Expected Output: [9, 7]
  • Justification: In this case, there are only two windows of size 4. The maximum value in the first window is 9 (from [9, 7, 2, 4]), and in the second window is 7 (from [7, 2, 4, 6]).

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Solution

To solve this problem, we'll use a deque (double-ended queue) to maintain the indices of the elements in the current window, ensuring the deque always has the maximum element's index at the front. This approach works because it allows us to efficiently remove elements that are no longer in the window (by checking if they are out of the current window's range) and ensure the first element in the deque is always the maximum of the current window. We'll iterate through the array, adding each element's index to the deque while maintaining these properties.

This method is effective because it combines the efficiency of a queue for managing the window's sliding mechanism with the ability to quickly update and retrieve the maximum value. By only storing relevant indices and removing those that are no longer in the window or are not potential maximums, we significantly reduce the time complexity compared to brute force methods that check every window's maximum separately.

Step-by-step Algorithm

  • Initialize an empty deque D to store indices of array elements.
  • Iterate through each element of the array nums:
    • If D is not empty and the front element of D is out of the current window's range (i - k), pop it from the front.
    • While D is not empty and the current element is greater than the element at the back of D, pop elements from the back. This ensures that the first element in D is always the maximum of the current window.
    • Add the current index i to the back of D.
    • If i is greater than or equal to k - 1, append the front element of D to the result array, as the window has now reached its full size.
  • Return the result array containing the maximums.

Algorithm Walkthrough

Let's consider the input: nums = [2, 1, 5, 1, 3, 2], k = 3

  1. Initialization:

    • The deque D is initialized as empty.
    • An empty result array is initialized to store the maximum of each window.
  2. Iteration 1 (i = 0, nums[i] = 2):

    • Since D is empty, add index 0 to D.
    • D now contains [0].
    • The window has not yet reached its full size (k = 3), so we don't add anything to the result array.
  3. Iteration 2 (i = 1, nums[i] = 1):

    • No indices are removed from D since all indices in D are within the current window's range.
    • nums[i] is less than nums[D.back()] (1 < 2), so just add index 1 to D.
    • D now contains [0, 1].
    • The window has not reached its full size, so no action on the result array.
  4. Iteration 3 (i = 2, nums[i] = 5):

    • No indices are removed from D for being out of range.
    • nums[i] is greater than nums[D.back()], so remove indices from D while nums[i] is greater than nums[D.back()]. Remove 0 and 1 from D.
    • Add index 2 to D since nums[2] is now the greatest so far.
    • D now contains [2].
    • The window has reached its full size. Add nums[D.front()] (which is 5) to the result array.
  5. Iteration 4 (i = 3, nums[i] = 1):

    • No indices are removed from D for being out of range.
    • nums[i] is less than nums[D.back()], so just add index 3 to D.
    • D now contains [2, 3].
    • Add nums[D.front()] (which is still 5) to the result array since the window is full.
  6. Iteration 5 (i = 4, nums[i] = 3):

    • No indices are removed from D for being out of range.
    • nums[i] is greater than nums[D.back()] (the index at D.back() is 3, and nums[3] is 1), so remove index 3 from D.
    • Add index 4 to D.
    • D now contains [2, 4].
    • Add nums[D.front()] (which is 5) to the result array.
  7. Iteration 6 (i = 5, nums[i] = 2):

    • Remove index 2 from D since it's out of the current window's range (i - k + 1 = 3).
    • nums[i] is less than nums[D.back()], so just add index 5 to D.
    • D now contains [4, 5].
    • Add nums[D.front()] (which is 3) to the result array.
  8. Final Result:

    • The result array, which contains the maximum of each window, is [5, 5, 5, 3].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • : Each element in the array is processed exactly twice - once when it's added to the deque and once when it's removed. This leads to a linear time complexity because the operations of adding to and removing from the deque (or its equivalent data structure) are O(1) operations.

Space Complexity

  • : In the worst-case scenario, the space complexity is due to the storage requirements of the result array, which contains at most N - k + 1 elements. The deque (or similar structure) itself will have at most k elements because it only stores elements from the current window. However, since k is a constant that does not scale with the input size N, the dominant term for space complexity is due to the output array, making it .
Sliding Window Maximum (hard)
Count Unique Characters of All Substrings of a Given String (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity